POI2008 Trains

POI
Treap, hash

POI20008 Trains

题目大意：

有n列火车，每列火车有L节车厢。每节车厢有一种颜色(用小写字母来表示)。有m次交换车厢的操作。求：对于每一列火车，在交换车厢的某一个时刻，与其颜色完全相同的火车最多有多少。

( $ 2 \le n \le 1000 $ , $ 1 \le L \le 100 $ , $ 0 \le m \le 100000 $ )

题解：

完全是码农题。。。

字符串hash是比较显然的。之后对于每一个hash值，我们建一棵Treap维护hash值为该值的字符串的下标。

用map来存每一棵Treap的根。

按照题目要求进行操作即可。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<map>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=1001,P=233;
int stk[N],top,ans[N];
struct Treap{
	struct node{
		int ch[2],key,val,sz,flag;
	}tree[N];
	void pushup(int&p){
		tree[p].sz=tree[tree[p].ch[0]].sz+tree[tree[p].ch[1]].sz+1;
	}
	void maintain(int&p,int flag){
		int val=tree[p].val;
		ans[val]=max(ans[val],flag);
		tree[p].flag=max(tree[p].flag,flag);
	}
	void pushdown(int&p){  
		if(!tree[p].flag)return;
		int ls=tree[p].ch[0],rs=tree[p].ch[1];
		if(ls)maintain(ls,tree[p].flag);
		if(rs)maintain(rs,tree[p].flag);
		tree[p].flag=0;
	}
	void rotate(int&p,int d){
		int k=tree[p].ch[d^1];
		pushdown(p),pushdown(k);
		tree[p].ch[d^1]=tree[k].ch[d];
		tree[k].ch[d]=p;
		pushup(p),pushup(k);p=k;
	}
	void insert(int&p,int x){
		if(!p){
			p=stk[top--];
			tree[p].key=rand(),tree[p].val=x,tree[p].sz=1;
			tree[p].ch[0]=tree[p].ch[1]=tree[p].flag=0;
		}else{
			pushdown(p);
			tree[p].sz++;
			bool d=x>tree[p].val;
			insert(tree[p].ch[d],x);
			if(tree[p].key<tree[tree[p].ch[d]].key)rotate(p,d^1);
		}
		pushup(p);
	}
	void erase(int&p,int x){
		pushdown(p);
		tree[p].sz--;
		if(tree[p].val==x){
			if(!tree[p].ch[0])stk[++top]=p,p=tree[p].ch[1];
			else if(!tree[p].ch[1])stk[++top]=p,p=tree[p].ch[0];
			else{
				bool d=tree[tree[p].ch[0]].key>tree[tree[p].ch[1]].key;
				rotate(p,d);erase(tree[p].ch[d],x);
			}
		}else{
			bool d=x>tree[p].val;
			erase(tree[p].ch[d],x);
		}
		if(p)pushup(p);	
	}
	int size(int p){
		return tree[p].sz;
	}
}T;
typedef unsigned long long ull;
map<ull,int>rt;
ull hash_val[N],p[101];
char str[N][101];
int n,l,m;
void INSERT(int x){
	T.insert(rt[hash_val[x]],x);
	int t=rt[hash_val[x]];
	T.maintain(t,T.size(t));
}
void DELETE(int x){
	T.erase(rt[hash_val[x]],x);
}
int main(){
	Rd(n),Rd(l),Rd(m);
	for(int i=n;i>=1;i--)stk[++top]=i;
	p[0]=1;
	for(int i=1;i<=l;i++)p[i]=p[i-1]*P;
	for(int i=1;i<=n;i++){
		scanf("%s",str[i]);
		for(int j=0;j<l;j++)
			hash_val[i]=hash_val[i]*P+str[i][j];
		INSERT(i);
	}
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		Rd(a),Rd(b),Rd(c),Rd(d);
		DELETE(a);
		if(a!=c)DELETE(c);
		hash_val[a]=hash_val[a]-p[l-b]*str[a][b-1]+p[l-b]*str[c][d-1];
		hash_val[c]=hash_val[c]-p[l-d]*str[c][d-1]+p[l-d]*str[a][b-1];
		swap(str[a][b-1],str[c][d-1]);
		INSERT(a);
		if(a!=c)INSERT(c);
	}
	for(int i=1;i<=n;i++)DELETE(i);
	for(int i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}
分享到 评论